Distributed data storage systems, such as those used in cloud computing environments, often rely on a metadata server to identify which servers store what data. This metadata server typically maintains a large metadata table mapping identifiers associated with data to the servers that store the data. Because of the large number of data units distributed among the storage servers, this metadata table can often be quite large. Also, to ensure durability of the data, data items are often stored across a plurality of server replicas. Metadata tables, then, often must identify a multiple servers for each data item identifier, greatly increasing the metadata table size. This large size makes it impractical to transmit the metadata table to the clients that will use the metadata table to identify servers. The other alternative is equally problematic: many servers frequently requesting server identifications from the single metadata server, thereby introducing congestion.
Besides these difficulties, metadata tables often suffer from poor durability and poor distribution of data among the servers. Servers are often assigned to data items in a naïve manner, allowing a single or dual server failure to cause permanent data loss even when three server replicas are assigned to a data item. Also, these naïve groupings often result in sub-optimal performance during recovery in the event of server failure, with only a small subset of the available servers participating in the recovery.